package 快排;

import java.util.Random;

public class Solution3 {
    public int[] inventoryManagement(int[] stock, int cnt) {
        int [] ret=new int[cnt];
        qsort(stock,0,stock.length-1,cnt);
        for(int i=0;i<cnt;i++){
            ret[i]=stock[i];
        }
        return ret;
    }

    private void qsort(int[] stock, int l, int r, int cnt) {
        int i=l;
        int left=l-1;
        int right=r+1;
        int key=stock[new Random().nextInt(r-l+1)+l];
        while(i<right){
            if(stock[i]<key){
                swap(stock,++left,i++);
            }else if (stock[i]==key){
                i++;
            }else {
                swap(stock,++right,i);
            }
        }
        int a=left-r+1;
        int b=right-left-1;
        if(a>cnt){
            qsort(stock,l,left,cnt);
        }else if(a+b>=cnt){
            return;
        }else {
            qsort(stock,right,r,cnt-a-b);
        }
    }
    private void swap(int[] nums, int i, int i1) {
        int tmp=nums[i];
        nums[i]=nums[i1];
        nums[i1]=tmp;
    }
}
